#!/usr/bin/env python3

class Node:
    def __init__(self, left=None, data=None, right=None):
        self.left = left
        self.data = data
        self.right = right

    def preorder_print(self):
        print(self.data, end=' ')
        if self.left is not None:
            self.left.preorder_print()

        if self.right is not None:
            self.right.preorder_print()



def getTrees(array, start, end):
    trees = []
    if end - start == 1:
        return [Node(data=array[start])]
    for x in range(start, end):
        leftTree = getTrees(array, start, x)
        rightTree = getTrees(array, x + 1, end)
        for left, right in _yield_one_case(leftTree, rightTree):
            root = Node(left, array[x], right)
            trees.append(root)
    return trees

def _yield_one_case(leftTree, rightTree):
    if len(leftTree) == 0:
        leftTree = [None]
    if len(rightTree) == 0:
        rightTree = [None]
    for left in leftTree:
        for right in rightTree:
            yield left, right


if __name__ == '__main__':
    array = [4, 5, 7]
    trees = getTrees(array, 0, len(array))

    print('[4, 5, 7]的可能二叉树的前序遍历结果: size: ', len(trees))
    for tree in trees:
        tree.preorder_print()
        print()
    print('\n================================================')
